import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * 56. 合并区间
 */
public class Solution_56 {
    /**
     * 官方题解
     * <p>
     * 时间复杂度：O(nlogn) + O(n) -> O(nlogn)
     * 空间复杂度：O(logn)，排序所需
     */
    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        // 将列表中的区间按照左端点升序排序
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return Integer.compare(o1[0], o2[0]);
            }
        });

        List<int[]> ans = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            if (ans.size() == 0 || ans.get(ans.size() - 1)[1] < left) {
                // 如果当前区间的左端点在数组 ans 中最后一个区间的右端点之后，
                // 那么它们不会重合，可以直接将这个区间加入数组 ans 的末尾
                ans.add(new int[] { left, right });
            } else {
                // 否则，它们重合，需要用当前区间的右端点更新数组 ans 中最后一个区间的右端点，
                // 将其置为二者的较大值
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], right);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }

    public static void main(String[] args) {
        Solution_56 solution = new Solution_56();
        int[][] intervals = { { 1, 9 }, { 2, 5 }, { 19, 20 }, { 10, 11 }, { 0, 3 } };
        int[][] ans = solution.merge(intervals);
        for (int i = 0; i < ans.length; i++) {
            System.out.println(Arrays.toString(ans[i]));
        }
    }
}